package com.fengye.algorithms.leecode.dp;

import java.util.Arrays;

/**
 * @author loupf50246
 * @date 2023/7/7 20:14
 */
public class NumDecoding91 {
    public static void main(String[] args) {
        System.out.println(numDecodingDP2("223"));
    }

    public static int numDecodingDP2(String s) {
        int length = s.length();
        int lastLast = 0;
        int last = 1;
        for (int i=0; i<length;i++) {
            int cur = 0;
            // 截取一个
            if (s.charAt(i) != 0) {
                cur = last;
            }

            // 截取2个是否符合
            if (i>=1 && (s.charAt(i-1) == '1'
                    || (s.charAt(i-1) == '2' && s.charAt(i) <= '6'))) {
                cur += lastLast;
            }
            lastLast = last;
            last = cur;
        }
        return last;
    }

    public static int numDecodingDP1(String s) {
        int length = s.length();
        // 类似青蛙跳台
        int[] dp = new int[length+1];
        dp[0] = 1;
        for (int i=1; i<=length;i++) {
            // 截取1个判断，只要不是0都符合
            if(s.charAt(i-1) != 0) {
                dp[i] += dp[i-1];
            }

            // 截取2个是否符合
            if (i>=2 && (s.charAt(i-2) == '1'
                    || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6'))) {
                dp[i] += dp[i-2];
            }
        }

        return dp[length];
    }

    public static int numDecoding(String s) {
        int[] map = new int[s.length()];
        //默认赋值-1
        Arrays.fill(map, -1);
        // 把它看成做一个遍历二叉树，index表示访问的字符位置
        return binaryTreeTraversal(s.toCharArray(), s.length(), map, 0);
    }

    public static int binaryTreeTraversal(char[] chars, int length, int[] map, int index) {
        // 递归终止的条件，到叶子节点，所有的字符都遍历完了
        // 说明找到了一种解码方式，返回1
        if (index >= length) {
            return 1;
        }

        // 查看计算过没，计算过了，就从map取
        if (map[index] != -1) {
            return map[index];
        }

        // 单个0不能构成字符，要跳过
        // 但两个数字的比如10、20是可以的
        // 两个数字的在上一步里截取
        if (chars[index] == '0') {
            return 0;
        }

        // 上面是二叉树遍历的终止条件，下面是截取

        // 截取一个数字的分支，类似于二叉树的左分支
        int res = binaryTreeTraversal(chars, length, map,index+1);

        // 截取两个数字的分支（类似于二叉树的右分支），截取两个数字
        // 必须要小于等于26
        if (index < length-1 && (chars[index] == '1'
                || (chars[index] == '2' && chars[index+1] <= '6'))) {
            res += binaryTreeTraversal(chars, length, map,index+2);
        }
        // 把计算结果放到map中
        map[index] = res;
        return res;
    }


    public static int numDecoding1(String s) {
        // 把它看成做一个遍历二叉树，index表示访问的字符位置
        return binaryTreeTraversal1(s.toCharArray(), s.length(), 0);
    }

    public static int binaryTreeTraversal1(char[] chars, int length, int index) {
        // 递归终止的条件，到叶子节点，所有的字符都遍历完了
        // 说明找到了一种解码方式，返回1
        if (index >= length) {
            return 1;
        }

        // 单个0不能构成字符，要跳过
        // 但两个数字的比如10、20是可以的
        // 两个数字的在上一步里截取
        if (chars[index] == '0') {
            return 0;
        }

        // 上面是二叉树遍历的终止条件，下面是截取

        // 截取一个数字的分支，类似于二叉树的左分支
        int res = binaryTreeTraversal1(chars, length, index+1);

        // 截取两个数字的分支（类似于二叉树的右分支），截取两个数字
        // 必须要小于等于26
        if (index < length-1 && (chars[index] == '1'
                || (chars[index] == '2' && chars[index+1] <= '6'))) {
            res += binaryTreeTraversal1(chars, length, index+2);
        }

        return res;
    }
}
